package DAlgorithm;

import java.util.Arrays;

public class DShellSort {

    public static void main(String[] args) {

        //初始化需要排序的数组
        int array[] = {9, 2, 11, 7, 12, 5};

        //初始化希尔排序的增量为数组长度
        int gap = array.length;

        //不断地进行插入排序，直至增量为1
        while (true) {
            //增量每次减半
            gap = gap/2;
            for (int i = 0; i < gap; i++) {
                //内部循环是一个插入排序
                for (int j = i + gap; j < array.length; j += gap) {
                    int temp = array[j];
                    int k = j - gap;
                    while (k >= 0 && array[k] > temp) {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = temp;
                }
            }
            //增量为1之后，希尔排序结束，退出循环
            if (gap == 1)
                break;
        }

        //打印出排序好的序列
        System.out.println(Arrays.toString(array));

    }
}
